A cloud service provider may host multi-zone and multi-tenant cloud servers. The cloud servers may host workloads for a tenant or a client of the cloud service provider. The cloud servers may provide access to the workloads to the client via multiple entry (and/or exit) points such as the internet, Multiprotocol Label Switching (MPLS), and MPLS-Virtual Private Network (MPLS-VPN). A firewall device associated with the cloud server may provide a client device access to only those workloads that the client device is authorized to access. The firewall device may provide such access, or alternately limit access, dynamically when the firewall device does not have any reachability information about the client device.